// 给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。
// 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
// 提示：
// 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
// 所有的机场都用三个大写字母表示（机场代码）。
// 假定所有机票至少存在一种合理的行程。
// 所有的机票必须都用一次 且 只能用一次。
// 示例 1：
// `输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] 输出：["JFK", "MUC", "LHR", "SFO", "SJC"]`
// 出发地和目的地可能是相同，所以需要去重

function findItinerary(tickets) {
    let result = ['JFK']
    let map = {}
    for (const ticket of tickets) {
        let [from, to] = ticket
        if (!map[from]) {
            map[from] = []
        }
        map[from].push(to)
    }
    for (const city in map) {
        map[city].sort()
    }
    
    function backtracking() {
        if (result.length === tickets.length + 1) {
            return true
        }
        let lastCity = result[result.length - 1]
        if (!map[lastCity] || !map[lastCity].length) {
            return false
        }
        for (let i = 0; i < map[lastCity].length; i++) {
            // 把已经用过的目的地删掉，防止死循环
            let city = map[lastCity][i]
            map[lastCity].splice(i, 1)
            result.push(city)
            if (backtracking()) {
                return true
            }            
            result.pop()
            map[lastCity].splice(i, 0, city)
        }
    }
    backtracking()
    return result
}

let tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
console.log(findItinerary(tickets))